package DataStructure.stack;

import java.util.Stack;

/**
 * 带通配号*的括号匹配
 * 题目简述：给定只包含'('、')'以及'*'字符的字符串，其中'*'字符可视为左/右括号或空字符，判断字符串是否是否满足括号匹配
 * 例：((((***)满足，(*)满足，**(不满足
 */
public class ParenthesisMatch2 {

    /**
     * 思路：双栈法。用两个栈分别存储'('和'*'及其所处的索引位置，扫描字符串，遇到'('和'*'则入对应栈，遇到')'则优先出栈'('进行匹配，若无才出栈'*'
     * 扫描完毕后，同时对两个栈逐步出栈比较栈顶字符索引，若栈顶'('索引大于'*'索引，则不能匹配
     * @return
     */
    public static boolean canMatch(String str) {
        Stack<Elem> stack1 = new Stack<>();
        Stack<Elem> stack2 = new Stack<>();
        for (int i = 0;i < str.length();i++) {
            char c = str.charAt(i);
            if (c == '(') stack1.push(new Elem('(', i)); //入栈
            else if (c == '*') stack2.push(new Elem('*', i));
            else {
                if (!stack1.isEmpty()) stack1.pop(); //优先出栈'('进行匹配
                else if (!stack2.isEmpty()) stack2.pop();
                else return false;
            }
        }
        //扫描完毕，同时对两个栈逐步出栈比较栈顶字符索引
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            //若栈顶'('索引大于'*'索引，则不能匹配
            if (stack1.pop().index > stack2.pop().index) return false;
        }
        return stack1.isEmpty();
    }

    static class Elem {
        char c;
        int index;

        public Elem(char c, int index) {
            this.c = c;
            this.index = index;
        }
    }

    public static void main(String[] args) {
        System.out.println(canMatch("((((***)"));
        System.out.println(canMatch("(*)"));
        System.out.println(canMatch("**("));
    }
}
